注意：本页面是由自动化程序生成的剪贴板存档。
#include <cstdio>
#define N 1000001
int rk[3*N+100], sa[3*N], bu[N], x[N], y[N];
void sort(int *rk, int *a, int *b, int n, int m) {
for (int i = 0; i <= m; i++) bu[i] = 0;
for (int i = 0; i < n; i++) bu[rk[a[i]]]++;
for (int i = 1; i <= m; i++) bu[i] += bu[i-1];
for (int i = n-1; i >= 0; i--) b[--bu[rk[a[i]]]] = a[i];
}
bool cmp3(int *r, int x, int y) {
return r[x] == r[y] && r[x+1] == r[y+1] && r[x+2] == r[y+2];
}
bool cmpt(int* r, int x, int y) {
if (r[x] != r[y]) return r[x] < r[y];
if (x%3 == 1) return bu[x+1] < bu[y+1];
else return !cmpt(r, y+1, x+1);
}
void DC3(int *rk, int *sa, int n, int m) {
bool h = (n%3 == 1); if (h) rk[n++] = 0;
int *rn = rk+n+2, *san = sa+n, ln = 0, p;
for (int i = 0; i < n; i++)
if (i % 3) x[ln++] = i;
rk[n] = rk[n+1] = 0;
sort(rk+2, x, y, ln, m);
sort(rk+1, y, x, ln, m);
sort(rk, x, y, ln, m);
int ta = 0, td = (n+1)/3;
#define F(x) (x/3)+(x%3==1?0:td)
rn[F(y[0])] = p = 1;
for (int i = 1; i < ln; i++) {
if (!cmp3(rk, y[i], y[i-1])) p++;
rn[F(y[i])] = p;
}
if (p < ln) DC3(rn, san, ln, p);
else for (int i = 0; i < ln; i++)
if (rn[i]) san[rn[i]-1] = i;
for (int i = 0; i < ln; i++)
if (san[i] < td) y[ta++] = san[i]*3;
sort(rk, y, x, ta, m);
#define G(x) (x>=td?(x-td)*3+2:x*3+1)
for (int i = 0; i < ln; i++)
bu[y[i] = G(san[i])] = i;
bu[n] = -1;
int i = 0, j = h; p = 0;
while (i < ta && j < ln) {
if (cmpt(rk, y[j], x[i])) sa[p++] = y[j++];
else sa[p++] = x[i++];
}
while (i < ta) sa[p++] = x[i++];
while (j < ln) sa[p++] = y[j++];
}
char s[N]; int n;
int main() {
scanf("%s", s);
for (n = 0; s[n]; n++)
rk[n] = s[n]-'0'+1;
DC3(rk, sa, n, 75);
for (int i = 0; i < n; i++)
printf("%d ", sa[i]+1);
puts("");
}